package com.wfm.leetcode.editor.cn;

import com.wfm.common.ListNode;
import org.junit.Test;

/**
 * 主要是快指针定位问题，先把fast指针定位到k+1的位置，然后慢快指针一起走
 * 总结一下：给你一个链表1 2 3 4 5，
 * 如果要返回第k个节点:while(cur!=null&&--k>0) cur=cur.next;
 * 如果要返回第k+1个节点：while(cur!=null&&k-->0) cur=cur.next;
 * 这里是--k和k--的问题
 * 由于本题是要定位倒数第k个节点，所以是顺数第n-k+1个节点
 */
public class BM8链表中倒数最后k个节点O22 {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && k-- > 0) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

    public ListNode getKthFromEnd2(ListNode head, int k) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast!=null&&k-->0){
            fast=fast.next;
        }
        while (fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
    @Test
    public void test(){
        ListNode kthFromEnd2 = getKthFromEnd2(ListNode.generalListNode(1, 5, 1), 2);
        ListNode.printListNode(kthFromEnd2);
    }
    @Test
    public void test2(){
        ListNode listNode = ListNode.generalListNode(1, 1, 1);
        ListNode.printListNode(listNode);
        ListNode kthFromEnd = getKthFromEnd(listNode, 1);
        ListNode.printListNode(kthFromEnd);
    }
}
